Не особо гарантирую, что всё верно

КМ      - NPC       сильно NPC      NP-hard
ЗР      - NPC
ВЫП     - NPC       сильно NPC      NP-hard
3-ВЫП   - NPC
БЛН     - NPC       сильно NPC

ЛН      - P
ЦЛН     - NPC       сильно NPC      NP-hard
ЛП      - P
ЦЛП     - NPC       сильно NPC      NP-hard

ПЧ      - NP и coNP

чётность, 2-выполнимость, делимость на 3 - P